package com.markus.code.剑指offer;

import java.util.HashMap;
import java.util.Map;

/**
 * Author:markusZhang
 * Date:Create in 2020/9/2 17:28
 * todo: 数组中数字出现次数II
 */
public class SingleNumberII {
    /**
     * 最简单的方式就是利用hashMap做统计
     */
    public int singleNumber1(int[] nums) {
        if (nums == null){
            return -1;
        }
        HashMap<Integer,Integer> numberMap = new HashMap<>();
        for (int num : nums) {
            Integer time = numberMap.containsKey(num)?numberMap.get(num)+1:1;
            numberMap.put(num,time);
        }
        for (Map.Entry<Integer, Integer> entry : numberMap.entrySet()) {
            if (entry.getValue() == 1){
                return entry.getKey();
            }
        }
        return -1;
    }
    /**
     * 下面来一个高效的模式，通过位运算来解决
     * 首先：我们遍历数字的二进制的每一位，这个数字能被三整除，那么它们这一位上的1的个数和也能被3整除
     * 最后如果这个和不能被3整除而是余出来一个的话，那么出现一次的数字该位上是1，否则是0
     */
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int i=0;i<32;i++){
            int cnt = 0;
            int one = 1<<i;
            for (Integer num : nums){
                //>0说明 该位不为1
                if ((num & one) > 0){
                    cnt++;
                }
            }
            //说明出现一次的那个数该位上是1
            if (cnt % 3 == 1){
                //拼装这个二进制数
                ans ^= one;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int []arr = {3,4,3,3};
        SingleNumberII demo = new SingleNumberII();
        System.out.println(demo.singleNumber(arr));
    }
}
